package br.puc.paa.graph.model;

import java.util.LinkedList;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x (unimplemented)
// Comparable find( x )   --> Return item that matches x
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// FONTE: http://users.cis.fiu.edu/~weiss/dsaajava/code/DataStructures/

/**
 * Implements an AVL tree.
 * Note that all "matching" is based on the compareTo method.
 * @author Mark Allen Weiss
 */
public class AvlTree
{
    /**
     * Construct the tree.
     */
    public AvlTree( )
    {
        root = null;
    }

    /**
     * Insert into the tree; duplicates are ignored.
     * @param x the item to insert.
     */
    public void insert( Integer x , Vertice v)
    {
    	System.out.println("Insert " + x + ", " + v);
    	AvlNode toBeInserted = new AvlNode(x, v);
        root = insert( toBeInserted, root );
    }

    /**
     * Remove from the tree. Nothing is done if x is not found.
     * @param x the item to remove.
     */
    public void remove( Integer x )
    {
        System.out.println( "Sorry, remove unimplemented" );
    }

    public void remove(AvlNode toBeRemoved)
    {
    	System.out.println("Remove " + toBeRemoved);
        root = remove(null, root, toBeRemoved);
    }
    
    public AvlNode remove(AvlNode parent, AvlNode current, AvlNode toBeRemoved )
    {
    	if (current == null) {
    		System.out.println("Avl node == null");
    	}
    	else {
    		System.out.println("Atual: "+ current.vertice + ", x= " + current.element 
    				+ "; a ser removido: " + toBeRemoved.vertice+ ", x= " + toBeRemoved.element);
    	}
        if (current.element == toBeRemoved.element && current.vertice.equals(toBeRemoved.vertice)) 
        {
        	// remove o elemento
        	if (parent == null) { // elemento é raiz
        		if( height( current.left ) - height( current.right ) == 2 )
                    if( current.compareTo( current.left ) < 0 )
                   	 current = rotateWithLeftChild( current );
                    else
                   	 current = doubleWithLeftChild( current );
        		else if( height( current.right ) - height( current.left ) == 2 )
                    if( current.compareTo( current.right ) > 0 )
                    	current = rotateWithRightChild( current );
                    else
                    	current = doubleWithRightChild( current );
        	} else if (parent.equals(current)) {
        		parent.left = current.right;
        		if (parent.left != null) {
        			parent.left.left = current.left;
        		} else {
        			parent.left = current.left;
        		}
        		current = parent;
        	} else {
        		parent.right = current.left;
        		if (parent.right != null)
        			parent.right.right = current.right;
        		else 
        			parent.right = current.left;
        		current = parent;
        	}
        	
        	
        } 
        else if (toBeRemoved.element.compareTo(current.element) < 0) {
        	current = remove(current, current.left, toBeRemoved);
        	 if( height( current.left ) - height( current.right ) == 2 )
                 if( current.element.compareTo( current.left.element ) <= 0 )
                	 current = rotateWithLeftChild( current );
                 else
                	 current = doubleWithLeftChild( current );
        }
        else if (toBeRemoved.element.compareTo(current.element) > 0) {
        	current = remove(current, current.left, toBeRemoved);
        	
        	if( height( current.right ) - height( current.left ) == 2 )
                if( current.element.compareTo( current.right.element ) > 0 )
                	current = rotateWithRightChild( current );
                else
                	current = doubleWithRightChild( current );
        }
        	
        
        return current;
    }
    
    /**
     * Find the smallest item in the tree.
     * @return smallest item or null if empty.
     */
    public Integer findMin( )
    {
        return elementAt( findMin( root ) );
    }

    public AvlNode findMinNode()
    {
        return findMin( root );
    }
    
    /**
     * Find the largest item in the tree.
     * @return the largest item of null if empty.
     */
    public Integer findMax( )
    {
        return elementAt( findMax( root ) );
    }

    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return the matching item or null if not found.
     */
    public Integer find( AvlNode node )
    {
        return elementAt( find( node, root ) );
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty( )
    {
        root = null;
    }

    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return root == null;
    }

    /**
     * Print the tree contents in sorted order.
     */
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }

    /**
     * Internal method to get element field.
     * @param t the node.
     * @return the element field or null if t is null.
     */
    private Integer elementAt( AvlNode t )
    {
        return t == null ? null : t.element;
    }

    /**
     * Internal method to insert into a subtree.
     * @param toBeInserted the item to insert.
     * @param t the node that roots the tree.
     * @return the new root.
     */
    private AvlNode insert( AvlNode toBeInserted, AvlNode t )
    {
    	
        if( t == null )
            t = toBeInserted;
        else if( toBeInserted.compareTo( t ) < 0 )
        {
            t.left = insert( toBeInserted, t.left );
            if( height( t.left ) - height( t.right ) == 2 )
                if( toBeInserted.compareTo( t.left ) < 0 )
                    t = rotateWithLeftChild( t );
                else
                    t = doubleWithLeftChild( t );
        }
        else if( toBeInserted.compareTo( t ) > 0 )
        {
            t.right = insert( toBeInserted, t.right );
            if( height( t.right ) - height( t.left ) == 2 )
                if( toBeInserted.compareTo( t.right ) > 0 )
                    t = rotateWithRightChild( t );
                else
                    t = doubleWithRightChild( t );
        }
            // Duplicate; add new vertice
        t.height = max( height( t.left ), height( t.right ) ) + 1;
        return t;
    }

    /**
     * Internal method to find the smallest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the smallest item.
     */
    private AvlNode findMin( AvlNode t )
    {
        if( t == null )
            return t;

        while( t.left != null )
            t = t.left;
        return t;
    }

    /**
     * Internal method to find the largest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the largest item.
     */
    private AvlNode findMax( AvlNode t )
    {
        if( t == null )
            return t;

        while( t.right != null )
            t = t.right;
        return t;
    }

    /**
     * Internal method to find an item in a subtree.
     * @param x is item to search for.
     * @param t the node that roots the tree.
     * @return node containing the matched item.
     */
    private AvlNode find( AvlNode toBeFound, AvlNode root )
    {
        while( root != null )
            if( toBeFound.compareTo( root ) < 0 )
            	root = root.left;
            else if( toBeFound.compareTo( root ) > 0 )
                root = root.right;
            else 
                return root;

        return null;   // No match
    }

    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the tree.
     */
    private void printTree( AvlNode t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }

    /**
     * Return the height of node t, or -1, if null.
     */
    private static int height( AvlNode t )
    {
        return t == null ? -1 : t.height;
    }

    /**
     * Return maximum of lhs and rhs.
     */
    private static int max( int lhs, int rhs )
    {
        return lhs > rhs ? lhs : rhs;
    }

    /**
     * Rotate binary tree node with left child.
     * For AVL trees, this is a single rotation for case 1.
     * Update heights, then return new root.
     */
    private static AvlNode rotateWithLeftChild( AvlNode k2 )
    {
        AvlNode k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
        k1.height = max( height( k1.left ), k2.height ) + 1;
        return k1;
    }

    /**
     * Rotate binary tree node with right child.
     * For AVL trees, this is a single rotation for case 4.
     * Update heights, then return new root.
     */
    private static AvlNode rotateWithRightChild( AvlNode k1 )
    {
        AvlNode k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
        k2.height = max( height( k2.right ), k1.height ) + 1;
        return k2;
    }

    /**
     * Double rotate binary tree node: first left child
     * with its right child; then node k3 with new left child.
     * For AVL trees, this is a double rotation for case 2.
     * Update heights, then return new root.
     */
    private static AvlNode doubleWithLeftChild( AvlNode k3 )
    {
        k3.left = rotateWithRightChild( k3.left );
        return rotateWithLeftChild( k3 );
    }

    /**
     * Double rotate binary tree node: first right child
     * with its left child; then node k1 with new right child.
     * For AVL trees, this is a double rotation for case 3.
     * Update heights, then return new root.
     */
    private static AvlNode doubleWithRightChild( AvlNode k1 )
    {
        k1.right = rotateWithLeftChild( k1.right );
        return rotateWithRightChild( k1 );
    }

      /** The tree root. */
    private AvlNode root;

    protected AvlNode getRoot() {
    	return root;
    }

    
    public AvlNode find(Vertice v) {
		System.out.println("Find " + v);
		LinkedList<AvlNode> queue = new LinkedList<AvlNode>();
		AvlNode node = getRoot();
		
		if (node == null)
			return null;
		
		queue.add(node);

		while (!queue.isEmpty()) {
			node = queue.remove();
			if (node.vertice.equals(v)) return node;
			if (node.left != null) {
				queue.add(node.left);
			}
			if (node.right != null) {
				queue.add(node.right);
			}
		}
		
		
		return null;
	}
        // Test program
    public static void main( String [ ] args )
    {
        AvlTree t = new AvlTree( );
        final int NUMS = 4000;
        final int GAP  =   37;

        System.out.println( "Checking... (no more output means success)" );

        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( new Integer( i ) , null );

        if( NUMS < 40 )
            t.printTree();
        if( t.findMin( ).intValue( ) != 1 ||
            t.findMax( ).intValue( ) != NUMS - 1 )
            System.out.println( "FindMin or FindMax error!" );

        /*for( int i = 1; i < NUMS; i++ )
             if( ((MyInteger)(t.find( new MyInteger( i ) ))).intValue( ) != i )
                 System.out.println( "Find error1!" );*/
    }
}